//给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 
//values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。 
//
// 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj =
// ? 的结果作为答案。 
//
// 返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替
//代这个答案。 
//
// 注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。 
//
// 注意：未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"]
//,["b","a"],["a","e"],["a","a"],["x","x"]]
//输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
//解释：
//条件：a / b = 2.0, b / c = 3.0
//问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
//结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
//注意：x 是未定义的 => -1.0 
//
// 示例 2： 
//
// 
//输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], 
//queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
//输出：[3.75000,0.40000,5.00000,0.20000]
// 
//
// 示例 3： 
//
// 
//输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],[
//"a","c"],["x","y"]]
//输出：[0.50000,2.00000,-1.00000,-1.00000]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= equations.length <= 20 
// equations[i].length == 2 
// 1 <= Ai.length, Bi.length <= 5 
// values.length == equations.length 
// 0.0 < values[i] <= 20.0 
// 1 <= queries.length <= 20 
// queries[i].length == 2 
// 1 <= Cj.length, Dj.length <= 5 
// Ai, Bi, Cj, Dj 由小写英文字母与数字组成 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 图 数组 最短路 👍 1021 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2023-10-03 18:09:22
 * @description 399.除法求值
 */
public class EvaluateDivision{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new EvaluateDivision().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //bfs
    public double[] calcEquation2(List<List<String>> equations, double[] values, List<List<String>> queries) {
		map=new HashMap<>();
		int size = equations.size();
		//保存节点和边权
		for (int i = 0; i < size; i++) {
			if(!map.containsKey(equations.get(i).get(0))){
				map.put(equations.get(i).get(0),new ArrayList<>());
			}
			if(!map.containsKey(equations.get(i).get(1))){
				map.put(equations.get(i).get(1),new ArrayList<>());
			}

			map.get(equations.get(i).get(0)).add(new Node(equations.get(i).get(1),values[i]));
			map.get(equations.get(i).get(1)).add(new Node(equations.get(i).get(0),1.0/values[i]));
		}
		int cnt=0;
		double [] res=new double[queries.size()];
		for (List<String> query : queries) {
			res[cnt++]=bfs(query);
		}
		return res;
	}
	private double bfs(List<String> query){
		//如果map中没有这两个点中的一个，则直接返回
		if(!map.containsKey(query.get(0))||!map.containsKey(query.get(1))) return -1.0;
		Set<String> set=new HashSet<>();
		Deque<Node> q=new LinkedList<>();
		//这里队列除了保存节点名，还需要保存此时的乘积
		q.offer(new Node(query.get(0),1.0));
		//标记是否访问
		set.add(query.get(0));
		while (!q.isEmpty()){
			Node poll = q.poll();
			if(Objects.equals(poll.id, query.get(1))) return poll.num;
			//访问领接节点
			for (Node node : map.get(poll.id)) {
				if(!set.contains(node.id)){
					q.offer(new Node(node.id,node.num* poll.num));
					set.add(node.id);
				}
			}
		}
		return -1.0;
	}
	/*dfs，把问题转化为带权的图，先构建，然后对每次查询遍历*/
		 Map<String,List<Node>>map;
	 public double[] calcEquation1(List<List<String>> equations, double[] values, List<List<String>> queries) {
		map=new HashMap<>();
		 int n=equations.size();
		 double [] res=new double[queries.size()];
		 //把节点和边权存储
		 for (int i = 0; i < n; i++) {
			 //被除数，除数
			 String dividend = equations.get(i).get(0);
			 String divisor = equations.get(i).get(1);

			 if(!map.containsKey(dividend)){
				 map.put(dividend,new ArrayList<>());
			 }
			 if(!map.containsKey(divisor)){
				 map.put(divisor,new ArrayList<>());
			 }
			 //放入边权
			 map.get(dividend).add(new Node(divisor, values[i]));
			 map.get(divisor).add(new Node(dividend,1.0/values[i]));
		 }

		 int cnt=0;
		 //遍历问题
		 for (List<String> query : queries) {
			 //深度，初始是1
			 res[cnt]=dfs(query.get(0), query.get(1),1.0,new HashSet<>());
			 cnt++;
		 }
		 return  res;
	 }
	 //当前节点，目标节点，之前的乘积结果，路径
	 private  double dfs(String cur, String dest, double pre, Set<String> set){
		 //如果map不包含当前节点，或者已经走过当前了，说明这条路走不通
		 if(!map.containsKey(cur)||set.contains(cur)){
			 return -1;
		 }
		 //走到了终点，返回
		 if(cur.equals(dest)) return pre;
		 //集合添加走过的节点
		 set.add(cur);
		 //遍历领接节点
		 for (Node node : map.get(cur)) {
			 //继续深度，倍数乘上一个节点的倍数
			 double temp=dfs(node.id,dest,pre*node.num,set);
			 //如果找到了答案，就返回
			 if(temp!=-1.0) return temp;
		 }
		 //没有找到
		 return -1.0;
	 }

	 class Node{
		 //领接节点代表的字符串
		 String id;
		 //边权
		 double num;
		 public Node(String i,double n){
			 id=i;
			 num=n;
		 }
	 }

	/*带权的并查集*/
	public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries){
		Map<String,Integer> hashmap=new HashMap<>();
		int size = equations.size();
		Union un=new Union(2*size);
		//变量名和id映射，方便并查集存储
		int id=0;
		for (int i = 0; i < size; i++) {
			List<String> eq = equations.get(i);
			String var1 = eq.get(0);
			String var2 = eq.get(1);
			if(!hashmap.containsKey(var1)){
				hashmap.put(var1,id++);
			}
			if(!hashmap.containsKey(var2)){
				hashmap.put(var2,id++);
			}
			un.union(hashmap.get(var1),hashmap.get(var2),values[i]);
		}

		//查询
		int cnt=0;
		double [] res=new double[queries.size()];
		for (List<String> query : queries) {
			String var1 = query.get(0);
			String var2 = query.get(1);

			Integer id1 = hashmap.get(var1);
			Integer id2 = hashmap.get(var2);
			if(id1==null||id2==null) res[cnt++]= -1.0d;
			else {
				res[cnt++]=un.isConnected(id1,id2);
			}
		}
		return res;
	}
	private class Union{
		private int[] parent;
		//指向父节点的权重

		private  double [] weight;

		public Union(int n){
			parent=new int[n];
			weight=new double[n];
			for (int i = 0; i < n; i++) {
				parent[i]=i;
				weight[i]=1.0d;
			}
		}

		public void union(int x,int y,double val){
			int rootX=find(x);
			int rootY=find(y);
			if(rootX==rootY) return;

			parent[rootX]=rootY;
			//value=x/y
			//即 x->rootX->rootY 等价于 x->y->rootY
			//weight[x]*weight[rootX]=value*weight[y]
			//weight[rootX]=weight[y]*value/weight[x]
			weight[rootX]=weight[y]*val/weight[x];
		}
		/*路径压缩*/
		public int find(int x){
			if(x!=parent[x]){
				int ori=parent[x];
				parent[x]=find(parent[x]);
				weight[x]*=weight[ori];
			}
			return parent[x];
		}
		//weigjt[x] 等于 x/root ,weight[y]等于 y/root,则 x/y=weight[x]/weight[y]
		public double isConnected(int x,int y){
			int rootX=find(x);
			int rootY=find(y);
			if(rootX==rootY){
				return weight[x]/weight[y];
			}else {
				return -1.0d;
			}
		}
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
